package link;



import java.util.HashSet;
import java.util.Set;

/**
 * 链表的常见操作
 * 1.链表的创建（单，双，循环）
 * 2.添加，插入、删除，输出
 * 3.反转，求中间节点，合并链表，判断成环
 *
 * FIFO （first in first out）
 * LFU   （Least Frequently used）
 * LRU  （least recently used）
 */
public class Solution {

    /**
     *
     * @param head 添加node
     * @param node
     */
    public static void add(ListNode head,ListNode node){
        head.next=node;
    }

    public static void add(ListNode head,int node){
        head.next=new ListNode(node);
    }

    /**
     * 插入倒数第二个位置
     * @param head
     * @param node
     */
    public static void addIndex(ListNode head,int node){
        ListNode pre=null;
        ListNode curr=head;
        while (curr.next!=null){
            pre=curr;
            curr=curr.next;
        }
        ListNode addNode = new ListNode(node);
        pre.next=addNode;
        addNode.next=curr;
    }

    /**
     * 删除结点  删除第一个匹配的结点
     * @param head
     * @param
     * @return
     */
    public static ListNode delNode(ListNode head, int node){
       if(head.val==node){ return head.next;}
       ListNode pre=head;
       ListNode curr=head.next;
       while (curr!=null&& curr.val!=node){
           pre=curr;
           curr=curr.next;
       }
       pre.next=curr.next;
       return  head;

    }

    /**
     * 206 链表反转
     */
    public static ListNode reverseList(ListNode head){

        ListNode pre=null;
        ListNode curr=head;
        while (curr!=null){
            ListNode next=curr.next;
            curr.next=pre;
            pre=curr;
            curr=next;
        }
        return pre;
    }
    /**
     * 141 链表有环 常规方法
     */
    public static boolean hasCycle1(ListNode head){
        Set<ListNode> set = new HashSet<>();
        while (head!=null){
            if(!set.add(head)){
                return true;
            }
            head=head.next;
        }
        return false;
    }
    /**
     * 141 链表有环，快慢指针
     */
    public static boolean hasCycle2(ListNode head){
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
    /**
     * 21
     */
    public static ListNode mergeTwoLists(ListNode l1,ListNode l2){
        if(l1==null){
            return l2;
        }else if(l2==null){
            return l1;
        }else if(l1.val<l2.val){
            l1.next=mergeTwoLists(l1.next,l2);
            return l1;
        }else{
            l2.next=mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
    /**
     * 21
     */
    public ListNode mergeTwoLists2 (ListNode l1,ListNode l2){
        ListNode prehead=new ListNode(-1);
        ListNode pre=prehead;
        while (l1!=null&&l2 !=null){
            if(l1.val<=l2.val){
                pre.next=l1;
                l1=l1.next;
            }else{
                pre.next=l2;
                l2=l2.next;
            }
            pre=pre.next;

        }
        pre.next=l1==null?l2:l1;
        return prehead.next;
    }

    /**
     * 876 中间结点,如果有两个中间结点，返回第二个结点  快慢指针
     *
     */
    public static ListNode midNode(ListNode head){
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }


    /**
     * 19 删除倒数第N个点
     * 先走n个点
     * 再遍历
     *
     */
    public static ListNode removeNthFromEnd(ListNode head,int n){
        ListNode front=head;
        ListNode back=head;
        ListNode bk=null;
        for (int i = 0; i <n-1 ; i++) {
            front=front.next;
            if(front==null){
                throw new RuntimeException("链表不足"+n+"个结点");
            }
        }
        while (front.next!=null){
            front=front.next;
            bk=back;
            back=back.next;
        }
        if(bk==null){
            return head.next;
        }else{
            bk.next=back.next;
            return head;
        }

    }

    /**
     * 打印链表
     * @param head
     */
    public static void print(ListNode head){
        System.out.print(head.val);
        while (head.hashNext()){
            System.out.print("->");
            head=head.next;
            System.out.print(head.val);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ListNode head = initNode1234();
//        testReverseList(head);
//        testHashCircle();
//        testMidNode(head);
//        testRemoveNthFromEnd(head,4);

//        testMergeTwoLists();
        testAddIndex(head);

    }
    public static void testAddIndex(ListNode head){
        addIndex(head,10);
        print(head);
    }

    public static void testMergeTwoLists(){
        ListNode node135 = initNode135();
        ListNode node246 = initNode246();
        print(mergeTwoLists(node135,node246));
    }

    public static void testRemoveNthFromEnd(ListNode head,int n){
        print(removeNthFromEnd(head,n));
    }

    public static void testMidNode(ListNode head){
        System.out.println(midNode(head).val);
    }

    public static void testReverseList(ListNode head){
                print(reverseList(head));
    }

    public static void testHashCircle(){
        ListNode head = new ListNode(1);
        ListNode second = new ListNode(2);
        ListNode third = new ListNode(3);
        ListNode forth = new ListNode(4);
        head.next= second;
        second.next=third;
        third.next=forth;
        boolean b = hasCycle1(head);
        System.out.println(b);
        forth.next=head;
        b = hasCycle1(head);
        System.out.println(b);
        b = hasCycle2(head);
        System.out.println(b);
    }

    public static ListNode initNode1234(){
        ListNode head = new ListNode(1);
        ListNode second = new ListNode(2);
        ListNode third = new ListNode(3);
        ListNode forth = new ListNode(4);
        head.next= second;
        second.next=third;
        third.next=forth;
        print(head);
        return head;
    }
    public static ListNode initNode135(){
        ListNode head = new ListNode(1);
        ListNode second = new ListNode(3);
        ListNode third = new ListNode(5);
        head.next= second;
        second.next=third;
        print(head);
        return head;
    }
    public static ListNode initNode246(){
        ListNode head = new ListNode(2);
        ListNode second = new ListNode(4);
        ListNode third = new ListNode(6);
        head.next= second;
        second.next=third;
        print(head);
        return head;
    }
}
